module examples.Sort where

--- Mische 2 sortierte Listen
merge ∷ (a→a→Ordering) → [a] → [a] → [a]    -- optionale Typdeklaration
merge comp xss yss = case xss of
    x:xs -> case yss of
        y:ys ->                             -- beide Listen sind nicht leer
            case comp x y of
                GT -> y : merge comp xss ys     -- y kommt zuerst, da x "größer" ist
                _  -> x : merge comp xs  yss    -- andernfalls x
        [] -> xss                           -- wenn eine der Listen leer ist
    [] -> yss                               -- ist die andere Liste das Ergebnis

--- Sortiere eine Liste _xs_ gemäß Vergleichsfunktion _comp_

sortBy ∷ (a→a→Ordering) → [a] → [a]    -- optionale Typdeklaration
sortBy comp []    = []      -- eine leere Liste ist schon sortiert
sortBy comp [x]   = [x]     -- ebenso eine mit nur einem Element
sortBy comp [x,y] =         -- zwei Elemente können wir direkt sortieren
    case comp x y of
        GT -> [y,x]            -- y kommt vor x
        _  -> [x,y]            -- sonst ist es andersrum
sortBy comp xs    =         -- sortieren und mischen der vorderen u. hinteren Hälfte
        merge comp (sortBy comp half1) (sortBy comp half2)
    where
        half1 = take n xs       -- vordere Hälfte
        half2 = drop n xs       -- hintere Hälfte
        n     = length xs `div` 2

--- Sortieren nach Ordnungsrelation des jeweiligen Typs 
sort ∷ Ord a ⇒ [a] → [a]
sort = sortBy compare

--- Eintrittspunkt
--- Hierfür wird ein "public static void main(String[] args) { ... }" generiert
main ∷ [String] → IO ()
main args = do
        println (sortBy (descending length) args)   -- absteigend nach Länge
        println (sort args)                         -- alphabetisch
    where
        descending f a b = compare (f b) (f a)  -- Argumente beim Vergleich vertauscht!
